#include <iostream>
#include <vector>

using namespace std;

class Solution 
{
public:
    int partition(vector<int>& a, int low, int high, int k)
    {
        int v = a[low];
        int i = low + 1;
        int j = high;
        while (true)
        {
            while (j >= low + 1 && a[j] < v)
                j--;
            while (i <= high && a[i] > v)
                i++;
            if (i > j)
                break;
            swap(a[i], a[j]);
            i++, j--;
        }
        swap(a[low], a[j]);
        
        if (j + 1 == k)
            return a[j];
        else if (j + 1 < k)
            return partition(a, j + 1, high, k);
        else
            return partition(a, low, j - 1, k);
    }
    int findKth(vector<int>& a, int n, int K)
    {
        return partition(a, 0, n - 1, K);
    }
};
int main()
{
    vector<int> v{ 10,10,9,9,8,7,5,6,4,3,4,2 };
    int n = 12;
    int k = 3;

    Solution xz;
    int m = xz.findKth(v, n, k);
    cout << m << endl;

	return 0;
}